package 面试经典150题.链表;

import common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author tmh
 * @date 2024/6/30 21:57
 * @description
 */
public class T105从前序与中序遍历序列构造二叉树 {
    Map<Integer, Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        //遍历中序数组 放在map里面
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //前序 后序 这样的排列顺序
        return findNode(preorder,0,preorder.length,inorder,0,inorder.length);
    }

    private TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
        //判断是否满足左闭右开的规则
        if(preBegin>=preEnd||inBegin>=inEnd){
            return null;
        }
        // 找到前序遍历的第一个元素在中序遍历中的位置
        Integer rootIndex = map.get(preorder[preBegin]);
        //  构造节点
        TreeNode root  =new TreeNode(inorder[rootIndex]);
        //保存中序左子树个数，用来确定前序数列个数
        int lenOfLeft = rootIndex - inBegin;
        //构建左子树  preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]  注意区间选择的范围
        root.left = findNode(preorder,preBegin+1,preBegin+lenOfLeft+1,inorder,inBegin,rootIndex);
        //构建右子树
        root.right = findNode(preorder,preBegin+lenOfLeft+1,preEnd,inorder,rootIndex+1,inEnd);
        return root;
    }
}
